Conventional networks such as the Internet are made of interconnected autonomous systems (AS). An autonomous system is a network under administrative control of a single entity, such as the network of a conventional Internet Service Provider (ISP). When coupled to other autonomous systems, each autonomous system becomes a portion of a larger network.
Each autonomous system is made up of communication equipment, including conventional routers. Routers that communicate between autonomous systems are described herein as edge routers (also known as border routers), and routers that communicate within an AS are referred to as internal routers.
Some of the internal routers in a conventional autonomous system are coupled to internal networks of one or more computer systems that are typically not under the control of the same entity that administers the AS, even though the internal network is said to be an internal network of that AS. For example, a customer of an AS may operate an internal network of that AS.
Routers in each AS can communicate topology and routing information via several protocols, including Interior Gateway Protocols (IGP) such as ISIS and OSPF and the conventional Internal Border Gateway Protocol ((I)BGP). IGP is used internal to the AS to provide topology information. Each router identifies itself as a node in the network and broadcasts information about the internal networks to which it is directly connected, as well as information about other routers to which it is directly connected, among other information. To compactly describe a large number of addresses, a range (i.e. a block) of addresses of each internal network may be communicated in the form of a prefix and a mask. An address of an internal network is within the range if the address of the internal network ANDed with the mask is equal to the prefix. Each router in an AS listens to this information and builds a complete topology map of the AS, including cost metrics for each link that are frequently inversely proportional to the bandwidth of the link, to allow the router to select the least cost route to any destination in the network. If a router receives a communication having an intended destination that is an address of an internal network of the AS, the router is able to forward the communication to the router directly connected to it that is on the least cost route to the intended destination specified in the communication. A router is directly connected to another router if communication between those two routers is not required to pass through another router. If there is more than one path possible to reach a particular destination, the manner in which the least cost path is selected can serve to allocate the traffic among the various paths to balance the utilization of all available paths according to the capacity of the path.
Information about inter-AS communications is communicated between autonomous systems via BGP and the BGP information is communicated within an AS using (I)BGP. BGP allows routers at the edge of each AS to describe to the edge router of another AS to which it is connected, all of the blocks of addresses with which it may communicate and the costs of doing so, using the prefix and mask technique described above. The BGP information received by each edge router of an AS is provided to all of the routers in the AS as (I)BGP information. This allows the routers in the AS to route communications intended for other autonomous systems to edge routers that can transmit the communication. Edge routers in an AS that receive this information via BGP as described above transmit it using (I)BGP messages to the other edge routers in the AS and/or to specialized devices known as route reflectors. If route reflectors are not used, certain of the edge routers are designated as BGP speakers to transmit the BGP information (in the form of (I)BGP messages) to the non-edge routers in the AS. Thus, either the BGP speakers or route reflectors take the (I)BGP messages from the edge routers and provide BGP information via (I)BGP messages to the internal routers in the AS.
When a device receives a communication that is to be forwarded to another AS, the device forwards the communication to the directly connected router in the least cost path that includes one of the edge routers that advertised itself via (I)BGP as being able to forward communications to that AS. As described above, the routing algorithms that select the least cost path can cause the traffic in an AS to utilize each link in the AS somewhat uniformly, so that for example, every link is utilized at approximately 40% of capacity.
However, there is a problem with this approach. If a communication is received for a destination, an edge router will prefer the path to another AS that communicates with that destination over an intra AS path that may support the same destination. Because the least cost paths are identified by the routers in an AS before the BGP information is added (the BGP information is added to the IGP information after the paths are calculated) if multiple edge routers communicate between a pair of autonomous systems, the utilization of the inter-AS links may not be balanced by the routing algorithms in the same manner that such utilization is balanced within the links of the AS.
It would be expensive to replace the routers in any autonomous system in order to solve these problems. Thus, it can be desirable that any solution to these problems be compatible with conventional routers.
What is needed is a method and system that can balance traffic among several paths between two autonomous systems in a manner that is compatible with existing router protocols.